using System;
using System.IO;
using System.Linq;
using System.Text;
namespace Aphalina.Compression
{
    public class HuffmanTree
    {
        private class Node
        {
            public HuffmanTree.Node Left
            {
                get;
                set;
            }
            public HuffmanTree.Node Right
            {
                get;
                set;
            }
            public int Code
            {
                get;
                set;
            }
            public int Bits
            {
                get;
                set;
            }
            public int Length
            {
                get;
                set;
            }
            public Node(int code)
            {
                this.Code = code;
            }
        }
        private HuffmanTree.Node root;
        private int[] codes;
        private int[] originalFreq;
        private HuffmanTree.Node[] nodes;
        public BitReader Reader
        {
            get;
            private set;
        }
        public BitWriter Writer
        {
            get;
            private set;
        }
        public int[] CodeLength
        {
            get;
            private set;
        }
        public int[] Freq
        {
            get;
            private set;
        }
        public int MaxCode
        {
            get
            {
                int num = this.nodes.Length;
                while (num > 0 && this.nodes[num - 1] == null)
                {
                    num--;
                }
                return num;
            }
        }
        public HuffmanTree(BitReader reader, int[] codeLength)
        {
            this.Reader = reader;
            this.CodeLength = codeLength;
            this.BuildTreeByCodeLength();
        }
        public HuffmanTree(BitWriter writer, int[] freq)
        {
            this.Writer = writer;
            this.Freq = freq;
            this.BuildTreeByFreq();
        }
        public void SaveTreeLength(string name)
        {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < this.CodeLength.Length; i++)
            {
                stringBuilder.AppendFormat("{0} - {1}\r\n", new object[]
				{
					i, 
					this.CodeLength[i]
				});
            }
            File.WriteAllText(name, stringBuilder.ToString());
        }
        public int ReadCode()
        {
            HuffmanTree.Node node = this.root;
            int num = 0;
            for (int i = 0; i < 32; i++)
            {
                num <<= 1;
                if (this.Reader.ReadBits(1) == 1)
                {
                    node = node.Right;
                    num |= 1;
                }
                else
                {
                    node = node.Left;
                }
                if (node.Code != -1)
                {
                    return node.Code;
                }
            }
            throw new Exception("InvaidCode");
        }
        public void WriteCode(int code)
        {
            this.Writer.WriteBits(this.nodes[code].Bits, this.nodes[code].Length);
        }
        public void BuildTreeByFreq()
        {
            this.codes = new int[this.Freq.Length];
            for (int i = 0; i < this.codes.Length; i++)
            {
                this.codes[i] = i;
            }
            this.originalFreq = new int[this.Freq.Length];
            if (Enumerable.Count<int>(this.Freq, (int e) => e != 0) < 2)
            {
                if (this.Freq[0] == 0)
                {
                    this.Freq[0] = 1;
                }
                else
                {
                    this.Freq[1] = 1;
                }
            }
            Array.Copy(this.Freq, this.originalFreq, this.Freq.Length);
            Array.Sort<int, int>(this.Freq, this.codes);
            this.root = new HuffmanTree.Node(-1);
            int num = 0;
            while (num < this.Freq.Length && this.Freq[num] == 0)
            {
                num++;
            }
            if (num < this.Freq.Length)
            {
                this.BuildTree(this.root, num, this.Freq.Length - 1);
                this.CodeLength = new int[this.Freq.Length];
                this.FillCodeLength(this.root, 0, 0);
                this.BuildTreeByCodeLength();
            }
        }
        private void BuildTree(HuffmanTree.Node node, int lbPos, int rbPos)
        {
            if (lbPos < rbPos)
            {
                int num = 0;
                int num2 = lbPos;
                int num3 = rbPos - 1;
                for (int i = num2; i <= num3; i++)
                {
                    num += this.Freq[i];
                }
                num /= 2;
                int num4 = 0;
                while (num2 < num3 && num4 + this.Freq[num2] < num)
                {
                    num4 += this.Freq[num2];
                    num2++;
                }
                node.Left = new HuffmanTree.Node(-1);
                node.Right = new HuffmanTree.Node(-1);
                this.BuildTree(node.Left, lbPos, num2);
                this.BuildTree(node.Right, num2 + 1, rbPos);
                return;
            }
            node.Code = this.codes[lbPos];
        }
        private void FillCodeLength(HuffmanTree.Node node, int code, int length)
        {
            if (node.Left != null)
            {
                this.FillCodeLength(node.Left, code << 1, length + 1);
                this.FillCodeLength(node.Right, code << 1 | 1, length + 1);
                return;
            }
            this.CodeLength[node.Code] = length;
        }
        public void BuildTreeByCodeLength()
        {
            int[] array = new int[32];
            for (int i = 0; i < this.CodeLength.Length; i++)
            {
                if (this.CodeLength[i] != 0)
                {
                    array[this.CodeLength[i]]++;
                }
            }
            int[] array2 = new int[32];
            int num = 0;
            for (int j = 1; j < array.Length; j++)
            {
                num = num + array[j - 1] << 1;
                array2[j] = num;
            }
            this.nodes = new HuffmanTree.Node[this.CodeLength.Length];
            this.root = new HuffmanTree.Node(-1);
            for (int k = 0; k < this.CodeLength.Length; k++)
            {
                int num2 = this.CodeLength[k];
                if (num2 != 0)
                {
                    HuffmanTree.Node node = this.root;
                    int num3 = array2[num2];
                    for (int l = this.CodeLength[k] - 1; l >= 0; l--)
                    {
                        if ((num3 >> (l & 31) & 1) == 0)
                        {
                            if (node.Left == null)
                            {
                                node.Left = new HuffmanTree.Node(-1);
                            }
                            node = node.Left;
                        }
                        else
                        {
                            if (node.Right == null)
                            {
                                node.Right = new HuffmanTree.Node(-1);
                            }
                            node = node.Right;
                        }
                    }
                    node.Code = k;
                    node.Bits = this.ReverseBits(num3, num2);
                    node.Length = num2;
                    this.nodes[k] = node;
                    array2[num2]++;
                }
            }
        }
        private int ReverseBits(int bits, int length)
        {
            int num = 0;
            for (int i = 0; i < length; i++)
            {
                num = (num << 1 | (bits & 1));
                bits >>= 1;
            }
            return num;
        }
    }
}
